package algorithm.niuke;

public class A最长递增子序列个数 {
    /*
     * 给定一个未排序的整数数组，找到最长递增子序列的个数。
     * 
     * 示例 1:
     * 
     * 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例
     * 2:
     * 
     * 输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
     */
    public int findNumberOfLIS(int[] nums) {
        // 最长递增子序列 dp[i] 以第i个数为结尾的最大递增子序列长度
        // 统计最长子序列的个数 count[i] 第i个数为结尾的递增子序列长度为dp[i]的 序列个数
        /*
         * 执行用时 : 36 ms , 在所有 Java 提交中击败了 41.96% 的用户 内存消耗 : 38.1 MB , 在所有 Java
         * 提交中击败了 75.00% 的用户
         */
        int len = nums.length;
        int[] dp = new int[len + 5];
        int[] counts = new int[len + 5];
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            int max = 1;
            int count = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < num) {
                    // 以第j个数结尾的序列+第i个数，组成新的递增序列
                    if (max == dp[j] + 1) {
                        count += counts[j];
                        continue;
                    }
                    if (max < dp[j] + 1) {
                        count = counts[j];
                        max = dp[j] + 1;
                    }
                }
            }
            dp[i] = max;
            counts[i] = count;
        }
        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, dp[i]);
        }
        int sum = 0;
        for (int i = 0; i < len; i++) {
            if (max == dp[i]) {
                sum += counts[i];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        A最长递增子序列个数 run = new A最长递增子序列个数();
        int[] nums = { 1, 2, 4, 3, 5, 4, 7, 2 };
        System.out.println(run.findNumberOfLIS(nums));
    }
}
